Evolvable Hardware or EHW is reconfigurable hardware that self-configures under the control of an evolutionary algorithm. In evolutionary electronics, the search for an electronic circuit reconfiguration can be made in software and the final solution downloaded or become a blueprint for hardware, which is referred to as extrinsic evolution. Alternatively, evolution can be performed directly in hardware, referred to as intrinsic evolution. With intrinsic evolution, solutions may be evolved directly on a chip.
The main steps of evolutionary synthesis are illustrated in FIG. 1. First, a population of chromosomes is randomly generated. The chromosomes are converted into circuit models for extrinsic EHW, or control bit strings downloaded to programmable hardware for intrinsic EHW. Circuit responses are compared against specifications of a target response, and individuals are ranked based on how close they come to satisfying it. In preparation for a new iteration loop, a new population of individuals is generated from the pool of best individuals in the previous generation, some of these individuals are taken as they were and some are modified by genetic operators such as chromosome crossover and mutation. This process is repeated for many generations, and results in increasingly better individuals. Such a process is usually stopped after a number of generations, or when the closeness to the target response has reached a sufficient degree. One of several solutions may be found among the individuals of the last generation.
A variety of circuits have been synthesized through extrinsic evolutionary means. For example, Koza et al., in U.S. Pat. No. 5,867,397, issued on Feb. 2, 1999, entitled, “METHOD AND APPARATUS FOR AUTOMATED DESIGN OF COMPLEX STRUCTURES USING GENETIC PROGRAMMING”, herein incorporated by reference in its entirety, used Genetic Programming (GP) to grow an “embryonic” circuit to a circuit that satisfies desired requirements. This approach was used for evolving a variety of circuits, including filters and computational circuits. An alternative encoding technique using a linear representation, which has the advantage of reduced computational load, has been used in for automated filter design.
With these extrinsic approaches, though, evolutions of analog circuits were performed in simulations, without concern of a physical implementation, but rather, as a proof-of-concept that evolution can lead to designs that compete or even exceed the performance of human designs. Although in principle, one can test their validity in circuits built from discrete components, or in an ASIC, no analog programmable devices exist that would support the implementation of the resulting design. Thus, these approaches do not provide a practical solution to intrinsic evolution.
Intrinsic evolution can speed-up the search for a solution circuit by a few orders of magnitude compared to evolution in software simulations, specifically if one simulates large, complex analog circuits, and if the circuit response is rapid. Moreover, since the software simulation relies on models of physical hardware with limited accuracy, a solution evolved in software may behave differently when downloaded in programmable hardware; such mismatches are avoided when evolution takes place directly in hardware. Further, unlike software evaluation where more complex circuitry and more accurate modeling takes longer to evaluate, hardware evolution scales well with both size of the circuits and model accuracy, thus providing less significant increases in evaluation time.
Although reconfigurable devices exist, they have a limited range of possible applications. On-chip evolution was demonstrated by A. Thompson, in Silicon Evolution, in Proceedings of Genetic Programming 1996 (GP96), MIT Press, herein incorporated by reference in its entirety, using a Field Programmable Gate Array or FPGA as a programmable digital device, and a Genetic Algorithm or GA as the evolutionary mechanism.
Such a technique using gate arrays, however, is not practical for analog circuit evolution. Logical gates are not good elementary building blocks for analog circuits as they are designed optimized for logical/binary behaviors. For example, transistor interconnections that are designed to facilitate digital logic signals and flows do not necessarily provide good analog response and signal flow. The usage of the gate array for evolution can result in exploitation by evolution, of parasitic and unintended signal paths and functioning modes for the components. As a result, circuits may evolve in one region of a chip that can not be replicated in other parts, or on other chips, although the same genetic code is used.
Moreover, conventional on chip evolution has not provided sufficient granularity for practical applications. While several levels of granularity are in use, the most common digital devices are configurable at the gate-level. In the analog programmable devices, such as in Field Programmable Analog Arrays or FPAAs, the reconfigurable active elements are Operational Amplifiers, which have only very coarse granularity and little functionality with good precision, thus having only a limited range of possible applications.
Computation by analog circuitry has been lost as a technique for information processing because analog circuits were not easily programmable, and required precise components with no drifts. If the evolutionary mechanism and process proves sufficiently powerful for evolving complex analog circuits, then its combination with reconfigurable analog devices potentially will be able to capture the benefits of analog in new applications. As such, the potential of analog processing is much greater than what is able to be exploited today.
Analog circuitry has advantages in cost, size and power consumption (as compared to digital circuitry) and can directly process signals that are continual in time and amplitude. Even a single transistor has many functions such as generation of square, square-root, exponential and logarithmic functions, voltage-controlled current sources; analog multiplication of voltages, and short term and long term analog storage. As such, the basic combinations of transistors offer a rich repertoire of linear and nonlinear operators available for local and collective analog processing. Using evolution, the benefits of analog processing can be exploited, while its disadvantages reduced or even eliminated.
Also, it has been recognized by the inventors herein that evolutionary searches may perform significantly better with analog than with digital circuitry. A possible explanation lies in the fact that analog behaviors have relatively smoother spaces, which is better for the evolutionary search. Thus, new perspectives are possible: evolutionary searches offering automatic programming; sufficiently precise equivalent components could be obtained if the programmable analog components offer controllability of their operating points; and drifts that can be compensated for by adjusting operating points or, if the drifts are too strong, by a new search for a different optimal circuit configuration and operating point. Moreover, analog computation on simple low-power circuits can boost emerging applications areas of “smart matter” and distributed high bandwidth adaptive sensing.
Furthermore, a hardware implementation also offers a big advantage in evaluation time for a circuit; the time for evaluation is determined by the goal function. For example, considering an A/D converter operating at a 100 kHz sampling rate, the electronic response of the A/D converter is available within 10 microseconds, compared to 1 second on a computer running SPICE; this advantage increases with the complexity of the circuits. In this case, the 1 speedup would allow evaluations of populations of millions of individuals in seconds instead of days. Moreover, the higher the frequency at which a circuit needs to function, the shorter is its evaluation time, making the design of very high frequency circuits an excellent candidate for intrinsic evolutionary design.
Thus, a practical solution to intrinsic evolution for programming analog devices is desirable. Furthermore, a shift in the design approach, from reconfigurable devices, to evolution-oriented devices or evolvable devices would facilitate hardware evolvability.